package com.lwg.datastructure.dynamicPrograming;

/**
 * @FileName: LongComSub.java
 * @Description: 最长公共子串
 * Copyright: Copyright(C) 2020-2022
 * Company  : Sunyard.hangzhou
 * @author: 李炜光
 * @slogan:
 * @Date: 2022/2/16 0016
 */
public class LongComSub {
    //示例
    //" 1 A B 2 3 4 5 C D"," 1 2 3 4 5 E F"
    // " 2 3 4 5 "
    public String LCS(String str1, String str2) {
        //定义dp[i][j] 表示str1中的第i个元素和str2中的第j个元素为最后一个元素组成的公共字符串个数
        //递推公式   dp[i][j]=dp[i-1][j-1]+1;
        // 1.最大长度
        int maxLength = 0;

        // 2.初始化最后一个相同字符的索引位置
        int maxLenIndex = 0;

        // 3.获得两个字符串的长度并初始化数组
        int n = str1.length();
        int m = str2.length();
        int dp[][] = new int[n + 1][m + 1];

        // 4.遍历循环两个字符串
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 5.找到字符串相同的位置
                if (str1.charAt(i) == str2.charAt(j)) {
                    //使用递推公式，因为j是从0开始的，所以
                    dp[i + 1][j + 1] = dp[i][j] + 1;

                    // 6.更新最大长度
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        // 7.更新最后字符的索引
                        maxLenIndex = i;
                    }

                }
            }
        }
        return str1.substring(maxLenIndex - maxLength + 1, maxLenIndex + 1);

    }
}